#include <stdio.h>
#include <iostream>
#include <string>
#include "CartesianTree.h"



int main() {


	CartesianTreeArray<int> testArray;

	std::string command;
	char c;
 	while (true) {

		command = "";
		while ( (c = getchar()) != ' ' ) {
			command = command + c;
		}

		if ( strstr( command.c_str(), "add" ) != 0 ) {
			int data = 0;
			scanf("%d", &data);
			testArray.Add(data);
			continue;
		} 
		if ( strstr( command.c_str(), "delete" ) != 0 ) {
			int index = -1;
			scanf("%d", &index);
			if ( (index >= 0) && (index < testArray.Size()) ) {
				testArray.Remove(index);
			} else {
				printf("Out of range\n");
			}
			continue;
		} 
		if ( strstr( command.c_str(), "insert" ) != 0 ) {
			int data = 0;
			int index = -1;
			scanf("%d %d", &index, &data);

			if ( (index >= 0) && (index < testArray.Size()) ) {
				testArray.Insert( index, data );
			} else {
				printf("Out of range\n");
			}
			continue;
		} 
		if ( strstr( command.c_str(), "sum" ) != 0 ) {
			int a = -1;
			int b = -1;
			scanf("%d %d", &a, &b);
			if ( (a >= 0) && (b < testArray.Size()) ) {
				printf("%d\n", testArray.GetSum(a, b + 1));
			} else {
				printf("Out of range\n");
			}
			continue;
		} 

	}
	
	return 0;
}

